package fun.coding.leetcode;

public class LongestCommonPrefix {

	public static void main(String[] args) {
		LongestCommonPrefix ins = new LongestCommonPrefix();
		String[] test1 = {"abc", "a", "abd"};
		System.out.println(ins.longestCommonPrefix(test1));
	}
	
	public String longestCommonPrefix(String[] strs) {
		StringBuilder sb = new StringBuilder();
		if (strs == null || strs.length == 0) return sb.toString();
		
		int l = strs.length;
		
		if (l == 1) return strs[0];
		
		while (true) {
			if (strs[0] == null || strs[0].length() == 0) return sb.toString();
			
			char c = strs[0].charAt(0);

			for (int i = 1; i < l; i++) {
				if (strs[i] == null || strs[i].length() == 0 || c != strs[i].charAt(0)) return sb.toString();
				
				strs[i] = strs[i].substring(1);
			}
			
			sb.append(c);
			strs[0] = strs[0].substring(1);
		}
	}
	/*
    // 1. Method 1, start from the first one, compare prefix with next string, until end;
    // 2. Method 2, start from the first char, compare it with all string, and then the second char
    // I am using method 1 here
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++) {
            int j = 0;
            while( j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
                j++;
            }
            if( j == 0) {
                return "";
	}
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
    */
}
